q21ubfandomcom-20200214-history
How can GPS devices be tracked from anywhere in the world?
The Automatic Packet Reporting System (APRS) is a digital communication system for real-time information exchange between amateur radio users in a local area. First developed by Bob Bruninga in the late 1980's, the system has grown to 40,000 users. APRS by Bob APRS handles the relay of many types of information, weather, traffic, alerts, and even text messaging. The most common type of data handled by the network is the GPS position of a mobile station. By using a network of digital repeaters (digipeaters) and internet connected receivers (i-gates) the system is able to relay this information to anywhere in the world without the use of a cellular network. Being a unique communication network, APRS has unique challenges and solutions to problems that will be discussed here. The Short Answer Network Overview The APRS network is formed by a number of nodes covering a local area with each node communicating with its nearest neighbors. Unlike other packet radio transmission protocols, APRS nodes broadcast in an unconnected manner. Rather than establishing a two-way connection between two users, all packets across the APRS network are sent with the ability for all receivers within range to hear. A digital repeater (digitpeater) will forward the packet to all the nodes with its range extending the range of the transmission beyond that which the original transmitter would be able to achieve. The packet will be forwarded several times until a limit set by the user is reached. It is likely that one of the receivers that intercepts the packet will be an APRS Internet Gateway (IGate) which will upload the data to the internet where it will be handled by the APRS Internet protocols and displayed on a website or sent to users connected to an APRS server. Automatic Packet Reporting System If a given local area has several digital repeaters any message sent will be received at multiple digipeaters and rebroadcast multiple times. These multiple transmissions increase the likelihood that a packet will be received over transmission in a non-broadcast manner. As we will examine, this protocol can also cause problems for the network when used in a dense area. Once uploaded to the internet duplicates of the same packet will be filtered out and the clean result can be displayed on a web page. If the packet is a message intended for another wireless user the APRS-IS network will forward the packet to the nearest IGate from which it will be transmitted wirelessly to the recipient. Packet Anatomy Packets sent through APRS use the AX.25 protocol designed for amateur radio use. AX.25 Link Access Protocol The protocol is able to transfer packets among nodes and detect errors in the communications channel. At each node the protocol is implemented with a Terminal Node Controller, a device containing a microcontroller running software to implement the protocol and a modem to convert between baseband digital information and modulated audio signals. The TNC is connected to a transceiver and is able to provide an interface to a user or be used autonomously to implement functions like in a digipeater. Many types of data are able to be sent through APRS. Weather, traffic, special alerts, and messages between users are all common transmissions. The network is bet known for its ability to process GPS data from a mobile station and provide the ability to track the station in real time from anywhere in the world. Websites such as findu.com and aprs.fi gather data from internet connected nodes throughout the network and display received GPS packets and the position of the station that sent them. Path Settings Since each digipeater acts autonomously there needs to be a control mechanism built into the packet to control how many times the packet is repeated across the network to prevent endless copies from being made. Each packet contains a path setting in WIDEn-N format where n is the number of times the user wishes the packet to be repeated and N is the number of times the packet has been repeated. When the packet is received at a digipeater the path setting is examined. If N=0 no action is taken. If N is not equal to zero, the packet is repeated with N decrimented by 1. APRS Paths and Digipeating We can distinguish between two types of digital repeaters. The first are the high power digipeaters that offer large coverage area and the second are lower power home-based "fill-in" digipeaters that do not have the same range capability as large digis, but can help fill in gaps in network coverage. If we want to first use one of these fill-in repeaters as a step onto the large coverage network we append WIDE1-1 to the end of our path setting. It is also worth noting that many digipeaters will add their callsign to a packet when it is repeated so that we may trace the path that each packet has taken through the network. This helps with determining the geographic area that the original station is in as well as help us diagnose problems in the network as will be seen later. The Long Answer Physical Characteristics The APRS network operates primarily on one frequency, 144.39MHz, making most digipeaters half-duplex. We will assume this is the case for all digipeaters in the following analysis. The data rate on this channel is 1200 baud. APRS from the Bottom Up Data is encoded using Audio Frequency Shift Keying (AFSK) where data is represented by shifts in tone of an audio signal. (Listen) Each packet lasts around one second. We usually denote average use in units of packets/30 minutes so we will denote capacity as the same, 1800 packets / 30 minutes. In reality due to physical constraints this maximum might be slightly less. Copies Made By Digipeating As mentioned before, each time a message is received by a repeater it is resent (assuming its path setting counter is not zero). Since the nodes work autonomously, a transmission will be repeated by every digi within its range. Let's assume that the distribution of digipeaters across a local area is symmetric. This is a valid approximation since digipeaters tend to be placed not in the immediate area of another, but in such a way as to fill in a gap in the network. We will assume that every digipeater can hear k'' others including the station that sent it the message. The calculations will be evaluated at each hop, denoted by ''t where t=1 after one hop, t=2 after two hops, and so on. APRS ALOHA Concept The first hop will be from the mobile station to all digipeaters within range l1=k The following hops will branch out, increasing the number of copies made with each hop. lt+1=lt+2(k) After N hops have been completed (as determined by the value of n that the user sets in the path setting) the number of copies of the packet that have been introduced into they system will be L = \sum^{N}_{t=1}lt Example Calculation 1 We can use this equation to do a calculation for the case where each digipeater can hear k=4 others and a path setting of WIDE2-2: After 1 hop: l1=k l1=4 After 2 hops: l2=l1+2(k)=4+8 l2=12 Total number of copies for WIDE2-2: L=l1+l2=4+12 L=16 If instead we used a path setting of WIDE3-3, the number of copies after 1 and 2 hops would be the same as before l1=4 l2=12 After 3 hops: l3=l2+2(k) =12+8 l3=20 Total number of copies after 3 hops: L=l1+l2+l3=4+12+20 L=36 Increasing the path setting just by one brings about a 125% increase in the number of copies. Probability of Packet Success As we have seen, increasing path setting will lead to many more copies of a packet being introduced into the network. This will have two effects from the view of the user who sends the packet: more packets being sent will increase the chances one of them is received, while at the same time, more packets in the network means a greater chance that the user's packets will not get through due to increased congestion. To view the user's best choice in this situation we define a utility function for which it is the user's goal to maximize. In this case, the utility function will simply be the probability that out of all the copies of one packet made at least one is successfully received. As mentioned before, the 1200 baud network takes about 1 second to process a packet. This means that the capacity of the channel C is an average 60 packets/minute. If we operate under capacity, we assume that no packets are lost due to congestion. However, if the number of packets sent is greater than the capacity of the channel we predict that we will loose some packets at a rate proportional to how many packets are in the network. If we let L denote the number of copies of a packet from the user for a given transmission and M denote the average number of packets that are in the network over a given period of time. Then the variable p_{sc} denotes the probability of success under congestion for one copy of a user's transmission to reach the intended destination. p_{sc} = \begin{cases} 1, C \geq (M+L) \\ \frac{C}{M+L}, otherwise \end{cases} As seen above, the process of repeating a packet does not introduce copies into the network evenly but rather an increasing number at each hop. To better model probability of success due to congestion we should make the variable dependent also on the number of hops that have occurred, t . Since M and C are given as averages over a certain time period (in this case lets say 60 seconds), then we can divide by the fraction of a minute it takes for the digipeater to process and repeat the packet at each hop, \Delta h . The result will be the average number of packets during the duration of one hop ct=\frac{C}{\Delta h} mt=\frac{M}{\Delta h} p_{sc}t = \begin{cases} 1, ct \geq (mt+lt) \\ \frac{ct}{mt+lt}, otherwise \end{cases} Thus we can see that as congestion increases the probability that the packet is successfully received decreases. Even with no congestion present the chances that a packet is received is not always 100% due to imperfections in the channel. We use a second parameter p_{sr} , the probability of success due to reliability of the channel, to model this. The overall probability that one packet is received is simply p_{pkt}t=p_{sr}p_{sc}t In order to compute the total probability that any packet from the transmission is received we use the a principle of statistics. Given independent events A and B that are not mutually exclusive the probability that A or B or both occurs is given by P(A \cup B) = P(A) + P(B) +P(A)P(B) If there are n number of independent events P(A \cup B \cup ... N) = 1-(1-PA)(1-PB)...(1-PN) And if the probability of each of n events is the same P_{total}= 1- (1-P)^N The probability of any packet being received is independent of the probability of another, making the events independent. However, both can be received at the same time (via different digipeaters) so we assume the events are not mutually exclusive. The probability that one or more packets created at hop t is received is then pt=1-(1-p_{pkt}t)^{lt} pt=1- \left( 1- \frac{p_{sr}C}{mt+lt} \right)^{lt} Notice that the number of copies of the user's packet appears in the equation twice, both increasing pt and decreasing pt. To calculate the total probability that any packet created at any hop is received, we do that same calculation using the independent probabilities from the previous step. P=1-(1-p1)(1-p2)...(1-pN) Example Calculation 2 Imagine a network with a 75% reliable channel, each digipeater is within range of k=4 others, and each hop takes 5 seconds. The capacity of the channel is C=60 packets/minute, M=C/2, and the user sets his path to WIDE2-2. \Delta h= \frac{60}{5}=12 ct=\frac{C}{\Delta h} = 5 mt = \frac{M} {\Delta h} = 2.5 At hop 1: l1=4 p_{sc}1=5/(2.5+4)=0.77 p_{pkt}1=(0.77)(0.75)= 0.59 At hop 2: l2=4+8=12 p_{sc}2=5/(2.5+12)=0.34 p_{pkt}2=(0.34)(0.75)=0.26 In total: p1=1-(1-0.58)^4=0.969 p2=1-(1-0.26)^{12}=0.973 P=1-(1-0.969)(1-0.973)=0.997 In this example, with a reliable channel and low congestion, the path setting of WIDE2-2 gives us a very high probability of success. To give a better overall view of the network, a MATLAB simulation was run with two channels and a varying N. The first had low congestion and a reliable channel. From this we learn that the effect of increasing the number of copies by using a wider path setting increases the probability of receiving a packet over that of lower path settings. In the case of the clean channel here, increasing beyond WIDE2-2 has no additional benefit to the user. The second channel examined has low reliability and has several times as many users than the channel allows. For the congested channel the user's motivation to use a wider path become more pronounced. A transmission using WIDE4-4 is 48% more likely to be received than a transmission using WIDE2-2. However, if all users think this way we create even more congestion and a lower probability of success. If users increase their path setting to compensate, the problem worsens. The Tragedy of the Commons This problem has been encountered before in our study of Networked Life. When users share a set of common resources if the negative externalities, the damage a user does to the system, does not also do equal or greater damage to the user the user may have the tendency to abuse the system. In this case, the user will have greater probability of a successful transmission when using wider path settings, especially under congestion. The user's best choice response ot increased congestion is to increase his path setting. However, if all users think this way the system will become less usable for all. In order for APRS to function, we must create cooperation among users to limit the amount of congestion put into the network due to repeated packets. For cooperation among users, the APRS network has some advantages over other networks such as the cell network. All amateur radio users must be licensed and are taught basic knowledge about best working with other users. Many of the network's users have an interest in the continued existence and success of the network, and may even help to maintain a part of the APRS network themselves. As mentioned before, in most areas of the country WIDE2-2 offers the best compromise between good probability of success and low congestion in the network with a few exceptions. In a geographic area where repeaters are less common, such as Wyoming, one might need a setting like WIDE3-3 in order to have good probability of success. In a very congested area such as Los Angeles, WIDE1-1 is likely sufficient. A solution that has been implemented in these high congestion areas has been to have digipeaters automatically cut down the path setting of a packet if it is above a certain threshold. If a user tries to use WIDE7-7 in such an area, the repeater may automatically reduce it to a more manageable setting such as WIDE2-2. Fixing Digipeaters The Aloha Circle Knowing the optimal path settings for one's current position is the best way to reduce congestion. Is there a more precise calculation for optimal path setting than guesswork? This is why the Aloha Circle concept was created. An Aloha Circle is a circle drawn on a map, centered on the user, with the radius equal to the farthest distance a user's transmission can be repeated before it begins to do damage to the network. The area of the Aloha Circle represents the maximum capacity of the local network, an average of 1800 packets / 30 minutes. The Aloha Circle calculation uses average packet transmission rates, which are approximately known for each type of user. The Aloha Circle The calculation is as follows: 1. Initialize a running total to zero and a multiplier to one. 2. Organize a list of the nearest stations by increasing distance from the user. 3. Beginning at the station closest to the user add the packets / 30 minutes to the running total for the type of station encountered. 4. If the last station was a digipeater, increase the multiplier by one. 5. For all following stations, multiply the average packets / 30 minutes by the multiplier before adding it to the running total. 6. When the running total reaches 1800, stop. The distance to that station is the radius of the Aloha Circle. 7. Adjust the user's path setting so that it is not repeated beyond the range of that circle to avoid adding unnecessary interference to the network. Example Calculation 3 An APRS client produces a list of the nearest stations to a mobile user. Calculate what the running total is at after these 12 stations have been added using the Aloha Circle calculation. C=1: (15+7+3)x1 = 25 Running Total = 25 C=2: (6+15+7+2+3)x2 = 66 Running Total = 91 C=3: (2+15+7+15)x3 = 117 Running Total = 208 After the twelve stations the running total is 208. Summary APRS is an interesting case study in network engineering. Since each digital repeater acts independently to forward every packet it receives, we must introduce a limit called a path setting on how many times a packet is repeated. The larger a path setting is the more copies of a packet are introduced into the network, increasing the user's probability of successful transmission but potentially reducing probability of other users' success. If each user does not take other users' needs into consideration while determining his path setting, the network will not function well. We can help guide each user by displaying an Aloha Circle, which defines the range that the user can safely transmit without adding unnecessary noise to the system. References Notes APRS is a registered trademark of APRS Softare and Bob Bruninga, WB4APR. Format adapted from "Networked Life: 20 Questions and Answers" by Mung Chiang, Cambridge University Press A presentation on this material is available here.